package com.it.data_tree.tree.binaryTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: Coke
 * @DateTime: 2023/04/15/10:44
 * @注释: 二叉树最大深度
 **/
public class MaxDepth {

    /*

     深度2    深度3         深度1
     1         1            1
    / \       / \
   2   3     2   3
                  \
                   4

    */
    
    /**
     * @param node:
     * @return int
     * @作者: Coke
     * @注释: 二叉树最大深度解法1 (使用递归)
     * @DateTime: 2023/4/15 11:20
     */
    /*
          1
         / \
        2   3
       / \
      4   5
    我们调用solution1函数，将根节点1作为参数传递进去。由于节点1不为空，所以进入函数体，计算其左子树和右子树的最大深度。

    对于左子树，节点1的左子节点是2，所以再次调用solution1函数，将节点2作为参数传递进去。节点2也不为空，所以进入函数体，继续计算它的左子树和右子树的最大深度。

    对于节点2的左子树，节点4是叶子节点，所以它的深度为1。同理，节点5的深度也为1。

    回到节点2，它的左子树深度为1，右子树深度也为1，所以它的最大深度为1 + 1 = 2。然后，函数继续计算节点2的右子树的最大深度。

    对于节点2的右子树，节点3是叶子节点，所以它的深度为1。

    回到节点1，节点1的左子树深度为2，右子树深度为0，所以它的最大深度为2 + 1 = 3。最后，函数返回3，表示整个树的最大深度为3。
     */
    public static int solution1(Node node) {
        if (node == null) {
            return 0;
        }
        // 分别求出左子树 和 右子树的最大深度
        int leftMax = solution1(node.getLeft());
        int rightMax = solution1(node.getRight());
        // 返回最大深度
        return Integer.max(leftMax, rightMax) + 1;
    }
    
    /**
     * @param node:
     * @return int
     * @作者: Coke
     * @注释: 二叉树最大深度解法2（不使用递归）
     * @DateTime: 2023/4/15 12:42
     */
   /*
     思路：使用非递归后序遍历，栈的最大高度即为最大深度
   */
    public static int solution2(Node node) {
        // 当前节点
        Node curr = node;
        // 栈弹出的元素
        Node pop = null;
        // 临时记录节点的栈
        LinkedList<Node> list = new LinkedList<>();
        // 记录最大值
        int max = 0;
        // 当前节点或者栈中有元素
        while (curr != null || !list.isEmpty()) {
            if (curr != null) {
                list.push(curr);
                max = Integer.max(list.size(), max);
                curr = curr.getLeft();
            } else {
                // 获取栈顶元素
                Node peek = list.peek();
                if (peek.getRight() == null || peek.getRight() == pop) {
                    pop = list.pop();
                } else {
                    curr = peek.getRight();
                }
            }
        }
        return max;
    }
    
    /**
     * @param node:
     * @return int
     * @作者: Coke
     * @注释: 二叉树最大深度解法3（层序遍历法 - 遍历一共有几层）
     * @DateTime: 2023/4/15 12:42
     */
   /*
     思路：使用非递归后序遍历，栈的最大高度即为最大深度
   */
    public static int solution3(Node node) {
        if(node == null){
            return 0;
        }
        // 使用队列记录每一层的节点
        Queue<Node> queue = new LinkedList<>();
        // 加入队列
        queue.offer(node);
        Node poll = null;
        // 记录最大值
        int max = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            max++;
            for (int i = 0; i < size; i++) {
                poll = queue.poll();
                System.out.print(poll.getNo() + "\t");
                if (poll.getLeft() != null) {
                    queue.offer(poll.getLeft());
                }
                if (poll.getRight() != null) {
                    queue.offer(poll.getRight());
                }
            }
            System.out.println();
        }
        return max;
    }
}
